All-pay auction

 ( All-pay Auction ) 

If player $i$ bids $b(x)$, he wins the auction only if his bid is larger than player $j$'s bid $b(v\_j)$. The probability for this to happen is

$\backslash mathbb\{P\}b(x)\; =\; \backslash mathbb\{P\}x\; =\; x$, since $b$ is monotone and $v\_j\; \backslash sim\; \backslash mathrm\{Unif\}0,1$

Thus, the probability of allocation of good to $i$ is $x$. Thus, $i$'s expected utility when he bids as if his private value is $x$ is given by

$u\_i(x|v\_i)=v\_ix-b(x)$.

For $b$ to be a Bayesian-Nash Equilibrium, $u\_i(x\_i|v\_i)$ should have its maximum at $x\_i\; =\; v\_i$ so that $i$ has no incentive to deviate given $j$ sticks with his bid of $b(v\_j)$.

$\backslash implies\; u\_i\text{'}(v\_i)\; =\; 0\; \backslash implies\; v\_i\; =\; b\text{'}(v\_i)$

Upon integrating, we get $b(v\_i)\; =\; \backslash frac\{v\_i^2\}\{2\}\; +\; c$.

We know that if player $i$ has private valuation $v\_i\; =\; 0$, then they will bid 0; $b(0)\; =\; 0$. We can use this to show that the constant of integration is also 0.

Thus, we get $b(v\_i)\; =\; \backslash frac\{v\_i^2\}\{2\}$.

Since this function is indeed monotone increasing, this bidding strategy $b$ constitutes a Bayesian-Nash Equilibrium. The revenue from the all-pay auction in this example is

$R=b(v\_1)+b(v\_2)=\backslash frac\{v\_1^2\}\{2\}+\backslash frac\{v\_2^2\}\{2\}$

Since $v\_1,\; v\_2$ are drawn iid from Unif0,1, the expected  revenue is

$\backslash mathbb\{E\}R=\backslash mathbb\{E\}\backslash frac\{v\_1^2\}\{2\}+\backslash frac\{v\_2^2\}\{2\}=\backslash mathbb\{E\}v^2=\backslash int\backslash limits\_\{0\}^\{1\}\; v^2dv\; =\backslash frac\{1\}\{3\}$.

Due to the revenue equivalence theorem, all auctions with 2 players will have an expected revenue of $\backslash frac\{1\}\{3\}$ when the private valuations are iid from Unif0,1.Algorithmic Game Theory. Vazirani, Vijay V; Nisan, Noam; Roughgarden, Tim; Tardos, Eva; Cambridge, UK: Cambridge University Press, 2007.  Complete preprint on-line at http://www.cs.cmu.edu/~sandholm/cs15-892F13/algorithmic-game-theory.pdf

Because the game is symmetric, the optimal bidding function must be the same for all players. Call this optimal bidding function $\backslash beta$. Because each player's payoff is defined as their expected gain minus their bid, we can recursively define the optimal bid function as follows:

$\backslash beta(v\_i)\; \backslash in\; arg\backslash max\_\{b\; \backslash in\; \backslash mathbb\{R\}\}\; \backslash left\backslash \{\backslash mathbb\{P\}(\backslash forall\; j\; \backslash neq\; i:\; \backslash beta(v\_j)\; \backslash leq\; b)v\_i\; -\; b\backslash right\backslash \}$

Note because F is smooth the probability of a tie is zero. This means the probability of winning the auction will be equal to the CDF raised to the number of players minus 1: i.e., $\backslash mathbb\{P\}(\backslash forall\; j\; \backslash neq\; i:\; \backslash beta(v\_j)\; \backslash leq\; \backslash beta(v\_i))\; =\; F(v\_i)^\{n\; -\; 1\}$.

The objective now satisfies the requirements for the envelope theorem. Thus, we can write:

This yields the unique symmetric Nash Equilibrium bidding function $\backslash beta(v\_i)$.

This is a typical model for all-pay auction. To calculate the optimal bid for each donor, we need to normalize the valuations {250, 500, 750} to {0.25, 0.5, 0.75} so that IPV may apply.

According to the formula for optimal bid:

$b\_i(v\_i)=\backslash left(\backslash frac\{n-1\}\{n\}\backslash right)\{v\_i\}^\{n\}$

The optimal bids for three donors under IPV are:

$b\_1(v\_1)=\backslash left(\backslash frac\{n-1\}\{n\}\backslash right)\{v\_1\}^\{n\}=\backslash left(\backslash frac\{2\}\{3\}\backslash right)\{0.25\}^\{3\}\; =\; 0.0104$

$b\_2(v\_2)=\backslash left(\backslash frac\{n-1\}\{n\}\backslash right)\{v\_2\}^\{n\}=\backslash left(\backslash frac\{2\}\{3\}\backslash right)\{0.50\}^\{3\}\; =\; 0.0833$

$b\_3(v\_3)=\backslash left(\backslash frac\{n-1\}\{n\}\backslash right)\{v\_3\}^\{n\}=\backslash left(\backslash frac\{2\}\{3\}\backslash right)\{0.75\}^\{3\}\; =\; 0.2813$

To get the real optimal amount that each of the three donors should give, simply multiplied the IPV values by 1000:

$b\_1real(v\_1=0.25)=\; \$10.4$

$b\_2real(v\_2=0.50)=\; \$83.3$

$b\_3real(v\_3=0.75)=\; \$281.3$

This example implies that the official will finally get $375 but only the third donor, who donated $281.3 will win the official's favor. Note that the other two donors know their valuations are not high enough (low chance of winning),  so they do not donate much, thus balancing the possible huge winning profit and the low chance of winning.